/*
 * arvore.c
 *
 *  Created on: 25/04/2011
 *      Author: joao
 */

#include <stdio.h>
#include <stdlib.h>

#include "arvore.h"


void insereBalanceado(int menor, int maior, no **raiz){
	int metade;

	if(menor==maior)
		BuscaInsere(menor, raiz);
	else{
		metade=(maior+menor)/2;
		BuscaInsere(metade, raiz);
		insereBalanceado(menor,metade-1,raiz);
		insereBalanceado(metade+1,maior,raiz);
	}

}

/* Rotacao a direita */

void rot_dir(no **p) {
  no *aux;
  aux = (*p)->esq;
  (*p)->esq = aux->dir;
  aux->dir = *p;

  *p = aux;
}

/* Rota��o � esquerda */

void rot_esq(no **p) {
  no *aux;
  aux = (*p)->dir;
  (*p)->dir = aux->esq;
  aux->esq = *p;

  *p = aux;
}

void insere_topo(int x, no **p) {
  /* Se a arvore esta vazia e facil inserir no topo */
  if (*p == NULL) {
    *p = (no *) malloc(sizeof(no));
    (*p)->info = x;

    /* Caso houvesse mais dados, copie-os aqui. */
    (*p)->dir = (*p)->esq = NULL;
  }
  else {
    if (x < (*p)->info) {
      insere_topo(x, &(*p)->esq);
      rot_dir(p);
    }
    else if (x > (*p)->info) {
      insere_topo(x, &(*p)->dir);
      rot_esq(p);
    }
  }
}


no *selecao(int k, no *raiz) {
  int t;

  /* Pode ser que o k-esimo elemento nao exista. */
  if (raiz->n_elem < k) return NULL;
  t = (raiz->esq == NULL) ? 0 : raiz->esq->n_elem;
  if (k < t + 1)
    return selecao(k, raiz->esq);
  if (k > t + 1)
    return selecao(k-t-1, raiz->dir);
  return raiz;
}

void sobe_menor(no **p) {
  if ((*p)->esq != NULL) {
    sobe_menor(&(*p)->esq);
    rot_dir(p);
  }
}

no *une_dir_esq(no *e, no **d) {
  /* Se a sub-arvore a direita eh vazia, retorna a outra. */
  if (*d == NULL) return e;
  sobe_menor(d);
  (*d)->esq = e;
  return *d;
}

void remove_no(int x, no **p) {
  no *aux;
  /* Verifica se o item esta na arvore. */
  if (*p == NULL) return;
  if (x < (*p)->info)
    remove_no(x, &(*p)->esq);
  if (x > (*p)->info)
    remove_no(x, &(*p)->dir);

  if (x == (*p)->info) {
    aux = *p;
    *p = une_dir_esq((*p)->esq, &(*p)->dir);
    free(aux);
  }
}

//aula passada

void P(no *p){
	printf("%d ", p->info);
}

void pre_ordem(no *raiz){
	if (raiz != NULL) {
		P(raiz);
		pre_ordem(raiz->esq);
		pre_ordem(raiz->dir);
	}
}

void in_ordem(no *raiz){
	if (raiz != NULL) {
		in_ordem(raiz->esq);
		P(raiz);
		in_ordem(raiz->dir);
	}
}

void pos_ordem(no *raiz){
	if(raiz != NULL){
		pos_ordem(raiz->esq);
		pos_ordem(raiz->dir);
		P(raiz);
	}
}

no  *busca(Tipo x, no *raiz){
	no *atual = raiz;

	while ((atual != NULL) && (atual->info != x))
    	if (x > atual->info) atual = atual->dir;
        else atual = atual->esq;
	return atual;
}


void BuscaInsere(Tipo x, no **p){

    if (*p==NULL) {  /* se o elemento nao foi encontrado, insere */
        *p = (no *)malloc(sizeof(no));
        (*p)->info = x;
        (*p)->esq = (*p)->dir = NULL;
        (*p)->cont = 1;
    }
    else
    	if (x<(*p)->info) BuscaInsere(x,&((*p)->esq));
    	else
    		if (x>(*p)->info) BuscaInsere(x,&((*p)->dir));
    		else
    			if (x == (*p)->info) (*p)->cont++;
}

/*void iniciaNovoNo (no **p){
	*p = (no *)malloc(sizeof(no));

	//(*p)->info = x;
	(*p)->esq = (*p)->dir = NULL;
	(*p)->cont = 1;
}*/

void imprime(no *raiz, int nivel) {
	/* Esta rotina e adequada para imprimir arvores com info de */
	/* comprimento maximo igual a 6 */
	int i;

	if (raiz == NULL) return;

	imprime(raiz->dir, nivel+1);

	for(i = 0; i < nivel; i++)
		printf("	");
	printf("%6d\n", raiz->info);

	imprime(raiz->esq, nivel+1);
}

void imprime2(no *raiz, FILE *saida) {
	/* Esta rotina e adequada para imprimir arvores com info de */
	/* comprimento maximo igual a 6 */


	if (raiz == NULL) return;

	imprime2(raiz->esq, saida);
	fprintf(saida, "%d %d\n", raiz->info, raiz->cont);
	imprime2(raiz->dir, saida);

}
